package oj;

import com.alibaba.fastjson.JSON;
import lombok.Data;

import java.util.*;

/**
 * @author chaolong.jin
 * @description
 * @date 2019/09/06 10:07
 */
@Data
public class N2 {
    private String name;

    public static void main(String[] args) {

        N2 n2 = new N2();
        int max = n2.maxSubArray(new int[]{1});
        System.out.println(max);
    }

    /**
     * 152. 乘积最大子序列
     *
     * @param nums
     * @return
     */
    public int maxMultiSubArray(int[] nums) {
        int[] m = new int[nums.length];
        m[0] = nums[0];
        int max = nums[0];
        int[] mulit = new int[nums.length];
        mulit[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            mulit[i] = mulit[i - 1] * nums[i];
        }
        for (int i = 1; i < nums.length; i++) {
            int temp = mulit[i];
            for (int j = 0; j < i; j++) {
                if (mulit[j] != 0) {
                    temp = max(mulit[i] / mulit[j], temp);
                } else {

                }
            }
            max = max(temp, max);
        }
        return max;
    }

    /**
     * 53. 最大子序和
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int[] m = new int[nums.length];
        m[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            m[i] = max(m[i - 1] + nums[i], nums[i]);
            max = max(m[i], max);

        }
        return max;
    }

    public int max(int a, int b) {
        return a > b ? a : b;
    }

    public ListNode rotateRight(ListNode head, int k) {
        int length = 0;
        ListNode cursor = head;
        while (cursor != null) {
            cursor = cursor.next;
            length++;
        }
        if (length <= 1) {
            return head;
        }
        int rotateStation = k % length;
        if (rotateStation == 0) {
            return head;
        }
        head = rotateMulti(head, rotateStation);
        return head;
    }

    /**
     * 双指针方式
     *
     * @param head
     * @param rotateStation
     * @return
     */
    public ListNode rotateMulti(ListNode head, int rotateStation) {
        ListNode cursor = head;
        ListNode rotateCursor = null;
        ListNode pre = null;
        ListNode tail = null;
        while (cursor != null && rotateStation-- > 0) {
            cursor = cursor.next;
        }
        //设置另外一个旋转指针
        rotateCursor = head;
        //cursor 到达末尾，旋转指针到达可以旋转的点
        while (cursor != null) {
            tail = cursor;
            cursor = cursor.next;
            pre = rotateCursor;
            rotateCursor = rotateCursor.next;
        }
        //断开指针
        pre.next = null;
        if (tail == null) {
            return rotateCursor;
        }
        //连接上一个指针
        tail.next = head;
        return rotateCursor;
    }

    private ListNode convertList(ListNode head) {
        ListNode result = null;
        ListNode rotateCursor = head;
        ListNode next = null;
        /**
         * 到达可旋转的指针，开始反转
         */
        while (rotateCursor != null) {
            next = rotateCursor.next;
            rotateCursor.next = result;
            result = rotateCursor;
            rotateCursor = next;
        }
        return result;
    }

    /**
     * 每次旋转一位
     *
     * @param head
     * @return
     */
    public ListNode rotateOne(ListNode head) {
        ListNode cursor = head;
        ListNode pre = null;
        while (cursor.next != null) {
            pre = cursor;
            cursor = cursor.next;
        }
        if (pre == null) {
            return cursor;
        }
        pre.next = null;
        cursor.next = head;
        return cursor;
    }

    public int strStr(String haystack, String needle) {
        int index = -1;
        char[] need = needle.toCharArray();
        char[] hay = haystack.toCharArray();
        int length = need.length;
        if (need.length < 1 && hay.length < 1) {
            return 0;
        }
        if (need.length < 1) {
            return index;
        }
        if (haystack.length() < 1) {
            return index;
        }
        char first = need[0];
        for (int i = 0; i < hay.length; i++) {
            while (i < hay.length && first != hay[i]) {
                i++;
            }
            if (i < hay.length) {
                int k = 0;
                for (; k < length && i < hay.length; k++) {
                    if (need[k] == hay[i]) {
                        i++;
                    } else {
                        break;
                    }
                }
                if (k == length) {
                    return i - k;
                }
            }
        }
        return index;
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode head = null;
        ListNode cursor = null;
        ListNode node = null;
        while ((node = minNode(lists)) != null) {
            if (cursor == null) {
                cursor = head = new ListNode(node.val);
            } else {
                cursor.next = new ListNode(node.val);
                cursor = cursor.next;
            }
        }
        return head;
    }

    //分支merge
    public ListNode mergeTwo(ListNode[] lists, int l, int r) {
        if (lists.length < 1) {
            return null;
        }
        if (r <= l) {
            return lists[l];
        }
        int mid = (l + r) / 2;
        ListNode list1 = mergeTwo(lists, l, mid);
        ListNode list2 = mergeTwo(lists, mid + 1, r);
        return merge(list1, list2);
    }

    private ListNode merge(ListNode headL, ListNode headR) {
        ListNode head = null;
        ListNode cursor = null;
        while (headL != null || headR != null) {
            if ((headR == null) || (headL != null && headL.val < headR.val)) {
                if (cursor == null) {
                    head = cursor = headL;
                } else {
                    cursor.next = headL;
                    cursor = cursor.next;
                }
                headL = headL.next;
            } else {
                if (cursor == null) {
                    head = cursor = headR;
                } else {
                    cursor.next = headR;
                    cursor = cursor.next;
                }
                headR = headR.next;
            }

        }
        return head;
    }

    public static ListNode minNode(ListNode[] lists) {
        int min = Integer.MAX_VALUE;
        int index = -1;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] == null) {
                continue;
            }
            if (lists[i].val < min) {
                min = lists[i].val;
                index = i;
            }
        }
        if (index == -1) {
            return null;
        }
        ListNode result = lists[index];
        lists[index] = lists[index].next;
        return result;
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cursor = head;
        ListNode nCursor = null;
        ListNode pre = null;
        ListNode result = head;
        while (n-- > 0) {
            cursor = cursor.next;
        }
        nCursor = cursor;
        //当nCursor 为null
        while (nCursor != null) {
            nCursor = nCursor.next;
            pre = head;
            head = head.next;
        }
        if (pre == null) {
            result = result.next;
        } else {
            pre.next = head.next;

        }
        return result;
    }

    public static String longestCommonPrefix(String[] strs) {
        String result = "";
        if (strs.length >= 1) {
            String s = strs[0];
            boolean flag = false;
            int i = 0;
            for (; i < s.length(); i++) {
                char c = s.charAt(i);

                for (int j = 1; j < strs.length; j++) {
                    if (strs[j].length() <= i) {
                        flag = true;
                        break;
                    }
                    if (c != strs[j].charAt(i)) {
                        flag = true;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
            result = s.substring(0, i);
        }
        return result;
    }

    public static String longestPalindrome(String s) {
        String result = "";
        char[] c = s.toCharArray();
        if (c.length < 1) {
            return "";
        }
        int resultLeft = 0;
        int resultRight = 0;
        for (int i = 0; i < c.length; i++) {
            int length1 = maxLength(s, i, i);
            int length2 = maxLength(s, i, i + 1);
            int max = Math.max(length1, length2);
            if ((resultRight - resultLeft) < max) {
                resultLeft = i - (max - 1) / 2;
                resultRight = i + max / 2;
            }
        }
        for (int i = resultLeft; i <= resultRight; i++) {
            result += c[i];
        }
        return result;
    }

    private static int maxLength(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(r) == s.charAt(l)) {
            l--;
            r++;
        }
        return r - l - 1;
    }

    public static int lengthOfLongestSubstring(String s) {
        char[] c = s.toCharArray();
        int max = 0;
        int start = 0;
        int end = 0;
        if (s.length() < 1) {
            return 0;
        }
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {

            Integer index = hashMap.get(c[i]);
            if (index == null || index < 0 || (index + 1) < start) {
                hashMap.put(c[i], i);
                end = i;
            } else {
                start = index + 1;
                hashMap.remove(c[i]);
                hashMap.put(c[i], i);
            }
            if (max < (end - start)) {
                max = end - start;
            }
        }
        return max + 1;
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode sumValue = null;
        ListNode head = null;
        int temp = 0;
        while (l1 != null || l2 != null || temp != 0) {
            if (l1 == null && l2 == null && temp != 0) {
                ListNode node = new ListNode(temp);
                sumValue.next = node;
                sumValue = sumValue.next;
                temp = 0;
                break;
            }
            int value = 0;
            if (l1 != null && l2 == null) {
                value = l1.val + temp;
                if (value >= 10) {
                    value -= 10;
                    temp = 1;
                } else {
                    temp = 0;
                }

            }
            if (l2 != null && l1 == null) {
                value = l2.val + temp;
                if (value >= 10) {
                    value -= 10;
                    temp = 1;
                } else {
                    temp = 0;
                }
            }
            if (l1 != null && l2 != null) {
                int sum = l1.val + l2.val + temp;
                if (sum >= 10) {
                    value = sum - 10;
                    temp = 1;
                } else {
                    temp = 0;
                    value = sum;
                }
            }
            ListNode node = new ListNode(value);
            if (sumValue == null) {
                sumValue = node;
                head = node;
            } else {
                sumValue.next = node;
                sumValue = sumValue.next;
            }
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        return head;
    }


    static class ListNode {
        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public static ListNode asList(int[] a) {
            ListNode listNode = null;
            ListNode head = null;
            for (int i = 0; i < a.length; i++) {
                if (listNode == null) {
                    head = listNode = new ListNode(a[i]);
                } else {
                    listNode.next = new ListNode(a[i]);
                    listNode = listNode.next;
                }
            }
            return head;
        }

        public void printList() {
            ListNode cursor = this;
            while (cursor != null) {
                System.out.print(cursor.val);
                cursor = cursor.next;
            }
            System.out.println();
        }
    }
}
